#include <iostream>
#include <chrono>
#include <mutex>

class Snowflake {
public:
    Snowflake(int64_t workerId, int64_t datacenterId)
        : workerId(workerId), datacenterId(datacenterId), sequence(0), lastTimestamp(-1) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw std::invalid_argument("workerId out of range");
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw std::invalid_argument("datacenterId out of range");
        }
    }

    int64_t nextId() {
        std::lock_guard<std::mutex> lock(mtx);

        int64_t timestamp = currentTimeMillis();

        if (timestamp < lastTimestamp) {
            throw std::runtime_error("Clock moved backwards. Refusing to generate id");
        }

        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = waitUntilNextMillis(lastTimestamp);
            }
        }
        else {
            sequence = 0;
        }

        lastTimestamp = timestamp;

        return ((timestamp - twepoch) << timestampLeftShift)
            | (datacenterId << datacenterIdShift)
            | (workerId << workerIdShift)
            | sequence;
    }

private:
    static constexpr int64_t twepoch = 1288834974657L;
    static constexpr int workerIdBits = 5;
    static constexpr int datacenterIdBits = 5;
    static constexpr int sequenceBits = 12;

    static constexpr int64_t maxWorkerId = (1 << workerIdBits) - 1;
    static constexpr int64_t maxDatacenterId = (1 << datacenterIdBits) - 1;
    static constexpr int64_t sequenceMask = (1 << sequenceBits) - 1;

    static constexpr int workerIdShift = sequenceBits;
    static constexpr int datacenterIdShift = sequenceBits + workerIdBits;
    static constexpr int timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    int64_t workerId;
    int64_t datacenterId;
    int64_t sequence;
    int64_t lastTimestamp;
    std::mutex mtx;

    int64_t currentTimeMillis() {
        return std::chrono::duration_cast<std::chrono::milliseconds>(
            std::chrono::system_clock::now().time_since_epoch()).count();
    }

    int64_t waitUntilNextMillis(int64_t lastTimestamp) {
        int64_t timestamp = currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = currentTimeMillis();
        }
        return timestamp;
    }
};
